import java.util.Arrays;

/**
 * @author LKQ
 * @date 2022/2/24 10:40
 * @description 动态规划
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {{1,1,1,-1,-1}, {1,1,1,-1,-1}, {-1,-1,-1,1,1}, {1,1,1,1,-1}, {-1,-1,-1,-1,-1}};
        solution.findBall(grid);
    }
    public int[] findBall(int[][] grid) {
        int n = grid[0].length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int j = 0; j < n; j++) {
            // 球的初始列
            int col = j;
            for (int[] row: grid) {
                int dir = row[col];
                col += dir;
                if (col < 0 || col == n || row[col] != dir) {
                    // 到达侧边或V形
                    col = -1;
                    break;
                }
            }
            if (col >= 0) {
                //成功到达底部
                ans[j] = col;
            }
        }
        return ans;
    }
}
